package leetcode101_xqzhao

// TODO 环形链表 II 【-】 单链表 | 脑筋急转弯

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		// fast.Next == nil 则直接返回, 继续执行会报空指针异常
		if fast.Next == nil {
			return nil
		}
		fast = fast.Next.Next
		if slow == fast {
			ptr := head
			for ptr != slow {
				// 相遇点一定在入环点
				ptr = ptr.Next
				slow = slow.Next
			}
			return ptr
		}
	}
	return nil
}
